1. Field of the Invention
The present invention relates to the field of directed graph traversal and more particularly to time estimation for traversing a directed graph.
2. Description of the Related Art
Process modeling and simulation relates to the modeling and simulation of dynamic or static systems, which can include, but are not limited to, enterprise management systems, engineering systems, networked information technology systems, utility systems, utility computing systems, autonomic computing systems, on-demand systems, electric power grids, biological systems, medical systems, weather systems, financial market systems, and business process systems. Such systems can be modeled and simulated for a variety of purposes including monitoring, analysis, control, design, simulation, and management.
A process model is an abstract description of a process such as a business process or any other process related to the lifecycle of a system. The abstract description of the process model can include sufficient detail required by a simulation engine for exercising the process model with one or more scenarios to determine a likely outcome. Process models generally specify one or more tasks or activities of a process and the relationship between the different tasks or activities. As part of the model, one or more events or conditions leading to the transition from one task or activity to the next can be specified. Models generally are expressed according to a specific format. Exemplary formats include Activity Decision Flow (ADF) Unified Modeling Language (UML) activity diagrams, and the Business Process Execution Language (BPEL), to name only a few.
Models are often expressed in the form of a directed graph. A directed graph is a graph whose edges are ordered pairs of vertices. That is, each edge can be followed from one vertex to another vertex. Directed graphs can be acyclic or cyclic. Cyclic directed graphs have at least one path that starts and ends at the same vertex. Acyclic directed graphs, in contrast, have no paths that start and end at the same vertex. In a directed graph, randomness can affect a path followed on any given traversal. For instance, decision points for respective vertices in a directed graph can result in different paths taken and for a cyclic directed graph, multiple iterations can occur though the number of iterations can vary from traversal to traversal depending upon the outcome at any given decision point in the directed graph.
At present, the execution time of a model can be simulated only through static time values assigned to each node in the model. Variability cannot be accommodated in consequence. To the extent that a model is expressed in the form of a directed graph, estimating execution time for the model can be highly dependent on the variable outcome of decision points in the model and the number of iterations transpiring in the course of the model execution. The very act of simulating a model, of course, also can consume time depending upon the processing resources consumed in the host computing environment. Accordingly, estimating the time remaining during the traversal of a directed graph can be an inexact science at best.